package com.leetcode;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No151
 * @description
 * @date 2021/1/27 下午5:02
 */
public class No151 {
    public static void main(String[] args) {
        String s = "  hello world!  ";
        s = s.trim();
        String res = reverseWords(s);
        System.out.println(res);
    }

    public static String reverseWords(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        char[] temp = s.toCharArray();
        // 整体翻转
        reverse(temp, 0, temp.length - 1);
        int i = 0;
        while (i < temp.length) {
            int j = i;
            while (j < temp.length && temp[j] != ' ') {
                j++;
            }
            // 部分翻转
            reverse(temp, i, j - 1);
            // 跳过空格
            while (j < temp.length && temp[j] == ' '){
                j++;
            }
            i = j;
        }
        StringBuilder str = new StringBuilder();
        // 添加
        i = 0;
        while (i < temp.length){
            if(temp[i] != ' '){
                str.append(temp[i]);
                i++;
            }else{
                while (i < temp.length && temp[i] == ' '){
                    i++;
                }
                str.append(" ");
            }
        }

        return str.toString();


    }

    private static void reverse(char[] temp, int i, int j) {
        while (i < j) {
            char t = temp[i];
            temp[i] = temp[j];
            temp[j] = t;
            i++;
            j--;
        }
    }

}
